import java.util.HashSet;
import java.util.Stack;

class LongestChain {
	private Queue q; // kö som används i breddenförstsökningen
	private Word goalWord; // slutord i breddenförstsökningen
	int wordLength;
	public static final char[] alphabet = { 'a', 'b', 'c', 'd', 'e', 'f', 'g',
			'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
			'u', 'v', 'w', 'x', 'y', 'z', 'å', 'ä', 'ö', 'é' };
	int alphabetLength = alphabet.length;

	public LongestChain(int wordLength) {
		this.wordLength = wordLength;
		q = new Queue();
	}
	
	// BreadthFirst utför en breddenförstsökning från startWord för att
	// hitta kortaste vägen till endWord. Den kortaste vägen returneras
	// som en kedja av ordposter (WordRec).
	// Om det inte finns något sätt att komma till endWord returneras null.
	public Word BreadthFirst(String startWord, String endWord) {
		boolean longestMode = false;
		if (endWord == null) {
			longestMode = true;
		}
		WordList.EraseUsed();
		Word start = new Word(startWord);
		WordList.MarkAsUsedIfUnused(start, null);
		goalWord = (longestMode) ? null : new Word(endWord);
		q.Empty();
		q.Put(start);
		Word longest = null;
		while (!q.IsEmpty()) {
			try {
				longest = (Word) q.Get();
				HashSet<Word> children = WordList.getChildren(longest);
				for (Word word : children) {
					if (WordList.MarkAsUsedIfUnused(word, longest)) {
						if (word.equals(goalWord)) {
							return word;
						}
						q.Put(word);
					}
				}
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		return (longestMode) ? longest : null;
	}

	public void CheckAllStartWords(String endWord) {
		Word finalChain = BreadthFirst(endWord, null);
		System.out.println(endWord + ": " + ChainLength(finalChain) + " ord");
		if (finalChain != null) {
			PrintWord(finalChain, true);
		}
	}

	public static int ChainLength(Word word) {
		int i = 1;
		while ((word = WordList.getParent(word)) != null) {
			i++;
		}
		return i;
	}

	public static void PrintWord(Word word, boolean backwards) {
		if (backwards) {
			System.out.print(word);
			while ((word = WordList.getParent(word)) != null) {
				System.out.print(" -> ");
				System.out.print(word);
			}
		} else {
			Stack<Word> q = new Stack<Word>();
			q.push(word);
			while ((word = WordList.getParent(word)) != null) {
				q.push(word);
			}
			try {
				System.out.print(q.pop());
				while (!q.empty()) {
					System.out.print(" -> ");
					System.out.print(q.pop());
				}
			} catch (Exception e) {
			}
		}
		System.out.println();
	}
}